package LeetCode;

/**
 * 174. 地下城游戏
 * https://leetcode.cn/problems/dungeon-game/description/
 */
class Solution1 {
    public int calculateMinimumHP(int[][] dungeon) {
        //1、创建dp表
        int row = dungeon.length;//行
        int col = dungeon[0].length;//列
        int[][] dp = new int[row + 1][col + 1];
        //2、初始化dp表
        for(int i = 0; i < col + 1; i++) {
            //初始化最后一行
            dp[row][i] = Integer.MAX_VALUE;
        }
        dp[row][col - 1] = 1;//最后一行的特殊位置
        for(int i = 0; i < row + 1; i ++) {
            //初始化最后一列
            dp[i][col] = Integer.MAX_VALUE;
        }
        dp[row - 1][col] = 1;//最后一列的特殊位置
        //3、填dp表(顺序：从右到左，从下到上)
        for(int i = row - 1; i >= 0; i--) {
            for(int j = col - 1; j >= 0; j--) {
                int min = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, min);
            }
        }
        //4、返回值
        return dp[0][0];
    }
}